% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

%\documentclass[letterpaper]{acm_proc_article-sp}
\documentclass{vldb}
\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)

%\documentclass[letterpaper]{sig-alternate}



%*************************************
%*************************************
%*************************************
%* To be removed in final version
%*************************************
%*************************************
%*************************************

% - Remove the word "full version (attached)"

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Add page numbers, remove copyright box.  For submitted version only.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  \pagenumbering{arabic}
  \makeatletter
  \makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Option 1 for removing copyright box. sig-alternate.cls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\def\@copyrightspace{\relax}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Option 2 for removing copyright box. sig-alternate.cls
% http://tex.stackexchange.com/questions/21536/how-to-remove-the-copyright-box-on-a-paper-that-uses-the-acm-sig-alternate-cls-c
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\usepackage{etoolbox}
\makeatletter
\patchcmd{\maketitle}{\@copyrightspace}{}{}{}
\makeatother
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: reduce the space between the author block and paper text? sig-alternate.cls
% http://tex.stackexchange.com/questions/57505/how-to-reduce-the-space-between-the-author-block-and-paper-text-sig-alternate-c
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\def\@maketitle{\newpage
% \null
% \setbox\@acmtitlebox\vbox{%
%\baselineskip 20pt
%\vskip 2em                   % Vertical space above title.
%   \begin{center}
%    {\ttlfnt \@title\par}       % Title set in 18pt Helvetica (Arial) bold size.
%    \vskip 1.5em                % Vertical space after title.
%%This should be the subtitle.
%{\subttlfnt \the\subtitletext\par}\vskip 1.25em%\fi
%    {\baselineskip 16pt\aufnt   % each author set in \12 pt Arial, in a
%     \lineskip .5em             % tabular environment
%     \begin{tabular}[t]{c}\@author
%     \end{tabular}\par}
%    \vskip 1.5em               % Vertical space after author.
%   \end{center}}
% \dimen0=\ht\@acmtitlebox
%% \advance\dimen0 by -12.75pc\relax % comment by Marco Daniel
% \unvbox\@acmtitlebox
% \ifdim\dimen0<0.0pt\relax\vskip-\dimen0\fi}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Smaller font for the reference section
% http://tex.stackexchange.com/questions/57525/smaller-font-for-the-reference-section
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\usepackage{etoolbox}
\apptocmd{\thebibliography}{\fontsize{8.2}{0}\selectfont}{}{}
%%\apptocmd{\thebibliography}{\scriptsize}{}{}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Set footnote size
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\renewcommand{\footnotesize}{\fontsize{8}{0}\selectfont}
%\renewcommand{\footnotesize}{\small}
%%\def\footnotesize{\@setsize\footnotesize{8pt}\viipt\@viipt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Reduce fontsize in \thanks
% have to put \thankssize in front of each text manually
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\newcommand{\thankssize}{\small}
%\newcommand{\thankssize}{\fontsize{8}{0}\selectfont}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Reduce margine
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[left=1in,top=1in,right=1in,bottom=1in]{geometry} % Does NOT work right now

%**************************************************
%**************************************************
%**************************************************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ADDITIONAL PACKAGES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\usepackage{epsfig}
%\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amstext}
\usepackage{amsmath}

%\usepackage{amsthm, thmtools} 
\usepackage{thmtools} 
\usepackage{colordvi}
\usepackage{color}

%\usepackage{ 
%nameref,%\nameref
%hyperref,%\autoref
%% n.b. \Autoref is defined by thmtools
%cleveref,% \cref
%% n.b. cleveref after! hyperref
%}



\usepackage{nameref}
\definecolor{ForestGreen}{rgb}{0.1333,0.5451,0.1333}
\definecolor{DarkRed}{rgb}{0.8,0,0}
\definecolor{Red}{rgb}{0.9,0,0}
\usepackage[linktocpage=true,
	pagebackref=true,colorlinks,
	linkcolor=DarkRed,citecolor=ForestGreen,
	bookmarks,bookmarksopen,bookmarksnumbered]
	{hyperref}
\usepackage{cleveref}

\usepackage{thm-restate} % See section 1.4 of the pdf above



%\usepackage{xspace}
%\usepackage{color}
\usepackage{algorithm}
\usepackage{algorithmicx}
%\usepackage[noend]{algpseudocode}
%\usepackage[algo2e,ruled,linesnumbered,vlined]{algorithm2e}
%\usepackage{comment}
\usepackage{enumitem}% http://ctan.org/pkg/enumitem
%\usepackage{subcaption}
%\usepackage{pstool}
%\usepackage{tabularx} %This package handles footnotes in tables correctly. Added by Danupon on March 20, 2013. 
%\usepackage{rotating}
%\usepackage[labelfont=bf]{caption}
%\usepackage{multirow}
%
%\newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]}


%
\usepackage{pifont,graphicx,subfigure}
\usepackage{epsfig,subfigure,url,latexsym,cite, color}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
%\numberwithin{algorithm}{section}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{amsmath}
%\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{amstext}
\usepackage{xspace}
\usepackage{pgfplots}
\usepackage{comment}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ADDITIONAL COMMANDS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\sketch#1{}
\def\note#1{}


%\def\danupon#1{{(\bf #1 --Danupon)}}
\def\danupon#1{}

%\def\danupon#1{\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
%\def\sketch#1{{\sf {\bf Sketch:} #1}}
%\def\note#1{{\bf  Note: #1}}

%\newtheorem{lemma}{Lemma}
%%\newtheorem{definition}{Definition}
%\newdef{definition}{Definition}
%\newtheorem{example}{Example}
%\newtheorem{corollary}[lemma]{Corollary}
%\newtheorem{theorem}[lemma]{Theorem}
%\newtheorem{claim}[lemma]{Claim}
%\newtheorem{observation}[lemma]{Observation}
%\newtheorem{conjecture}{Conjecture}


\declaretheorem[numberwithin=section]{theorem}
\declaretheorem[numberlike=theorem]{lemma}
\declaretheorem[numberlike=theorem]{corollary}
\declaretheorem[numberlike=theorem]{proposition}
\declaretheorem[numberlike=theorem,refname={fact,facts},Refname={Fact,Facts}]{fact}
\declaretheorem[numberlike=theorem,refname={observation,observations},Refname={Observation,Observations}]{observation}
\declaretheorem[numberlike=theorem,name={Algorithm},refname={algorithm,algorithms},Refname={Algorithm,Algorithms}]{algothm}
\declaretheorem[numberlike=theorem,name={Claim},refname={Claim,Claims},Refname={Claim,Claims}]{claim}


\newcommand{\reals}{{\mathbb R}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\opt}{{\sf OPT}}
\newcommand{\p}{{\sf P}}
\newcommand{\np}{{\sf NP}}
\newcommand{\rev}{\operatorname{rev}}
%\newcommand{\squishlist}{
% \begin{list}{$\bullet$}
%  { \setlength{\itemsep}{0pt}
%     \setlength{\parsep}{3pt}
%     \setlength{\topsep}{3pt}
%     \setlength{\partopsep}{0pt}
%     \setlength{\leftmargin}{1.5em}
%     \setlength{\labelwidth}{1em}
%     \setlength{\labelsep}{0.5em} } }
%\newcommand{\squishend}{
%  \end{list}  }

\newcommand{\squishlist}{
 \begin{itemize}}
\newcommand{\squishend}{
  \end{itemize}  }


\renewcommand{\paragraph}[1]{\medskip\noindent{\bf #1.}\xspace}

\begin{document}

%\title{Interactive Regret Minimization\titlenote{(Does NOT produce the permission block, copyright information nor page numbering). For use with ACM\_PROC\_ARTICLE-SP.CLS. Supported by ACM.}}

%\title{Social Network Monetization via the Spread of Influence: the Provider's Perspective}
%\title{Sponsored Viral Marketing on Social Networks: the Provider's Perspective}

\title{Maintaining the Densest Subgraph Over Time}

%\subtitle{[Extended Abstract]
%\titlenote{A full version of this paper is available as \textit{Author's Guide to Preparing ACM SIG Proceedings Using \LaTeX$2_\epsilon$\ and BibTeX} at \texttt{www.acm.org/eaddress.htm}}}

%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.

\author{
\alignauthor Atish {Das Sarma}\\ \affaddr{eBay Research Labs, eBay Inc., San Jose, USA}\\ \email{atish.dassarma@gmail.com}
\and
\alignauthor Ashwin Lall\\ \affaddr{Denison University, Granville, Ohio, USA}\\ \email{lalla@denison.edu}\\
%
\alignauthor Danupon Nanongkai\thanks{Part of this work was done while D. Nanongkai was at Nanyang Technological University, Singapore, and ICERM, Brown University, USA.}\\ \affaddr{University of Vienna, Austria}\\ \email{danupon@gmail.com}
}



\maketitle
\input{abstract}

%\begin{abstract}
%TO DO
%\end{abstract}%

% A category with the (minimum) three required fields
%\category{H.2.4}{Database Management}{Systems}[Query processing]
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Theory}

% \keywords{Skyline, Top-$k$, Regret Minimization} % NOT required for Proceedings

\input{introduction}
\input{related}
\input{algorithm}
\input{experiments}
\input{conclusions}


\bibliographystyle{abbrv}
\bibliography{dense}

%\newpage
%\appendix
%\input{detailed_definitions}
%\input{omit_proofs}


\end{document}
